Privacy and anonymity have become major concerns as people become increasingly dependent on the Internet in their daily lives. For example, people sometimes do not want others to know what Web sites they have visited. Under certain circumstances, people want to remain anonymous to the Web sites they have visited so that their personal interests can not be profiled by the Web sites. To address these privacy concerns, a number of anonymous communication systems (e.g. DC-Net [7] Anonymizer.com [1], Crowds [25], Onion Routing [24], Tor [9], Hordes [27], Web Mixes [3]) have been designed to provide anonymity to the communicating parties.
According to Pfitzmann and Waidner [23], there are three types of anonymities that can be provided by anonymous communication systems: sender anonymity, receiver anonymity, and unlinkability of sender and receiver. Sender anonymity means that the identity of the information sender is hidden, and receiver anonymity means that the identity of the information receiver is hidden. Unlinkability of sender and receiver refers to the property that the sender and receiver of a communication cannot be identified even if the sender and receiver are known to be of communicating with someone. Since anonymity is the state of lacking identity, anonymous communication can only be achieved by removing all the identifying characteristics from the anonymized network flows.
It's well known that encryption alone is not adequate to achieve anonymity. For example, various traffic analysis techniques [33, 32, 10, 31, 30] have been shown to be able to uniquely identify encrypted flows. These traffic analysis techniques can be used to link the encrypted flow to its original information sender and receiver, which would break the sender and receiver anonymity as well as the unlinkability of sender and receiver.
Traditional methods of achieving anonymity in communication include using proxies [24, 25, 9], MIXes [6, 17, 3], and various other flow transformations such as adding cover traffic, packet dropping, flow mixing, flow splitting, and flow merging. Since these flow transformations drastically change the original network flow, it is generally believed that these flow transformations would remove most, if not all, identifying characteristics of the original flow and make it indistinguishable from some other independent network flow. For example, cover traffic has long been believed to be able to prevent the adversary from using traffic analysis to uniquely identify the covered flow and link the information sender and receiver. A number of works [16, 15, 12] have used cover traffic to achieve anonymity. In addition, Blum et al. [5] claimed that a packet flow would become indistinguishable from other independent packet flows if the ratio of the cover traffic added to the original flow reaches certain threshold. They further claimed that their hardness result regarding the traffic analysis holds true even if the adversary is active.
There are fundamental limitations of flow transformations in anonymizing packet flows by taking the role of active adversary. What is needed is a mechanism for uniquely identifying a packet flow in spite of various flow transformations that may be used to link an anonymized packet flow to its original flow thus breaking the anonymity of the packet flow.